//
// Created by 子夜求知 on 2022/9/7.
//

#ifndef TREEPROJECT_LINKLIST_H
#define TREEPROJECT_LINKLIST_H
/**
 * 链表的结点结构体
 */
typedef struct linknode {
    int data;
    struct linknode *next;
} *linklist,linknode;

/**
 * 打印链表数据
 */
void printLinkList(linklist head){
    // 打印链表
    linknode *p = head;
    while (p !=NULL){
        printf("%d ",p->data);
        p = p->next;
    }
}

/**
 * 根据数组数据创建链表
 * @return
 */
linklist createLinkList(){
    // 根据list数组创建链表
    int list[] = {1,4,6,8,9,1,4,9,3};
    linklist head = (linknode*)malloc(sizeof (linknode));
    head->next = NULL;
    head->data = list[0];
    int i;
    for ( i = (sizeof (list)/sizeof (int))-1; i > 0 ; i--) {
        linknode *node = (linknode*)malloc(sizeof (linknode));
        node->data = list[i];
        node->next = head->next;
        head->next = node;
    }

    printLinkList(head);
    return head;
}

/**
 * 设计在单链表中删除相同多余结点的算法
 * 算法思想：
 * 用cur指针遍历该链表所有的结点
 * 用一个cur指针指向当前结点，用p结点遍历除cur结点之外所有的结点，如果值相等则删除该结点
 * @param head
 */
void delRedundant(linklist head){
    linknode *p = NULL;
    linknode *cur = NULL;
    cur = head;
    while (cur!=NULL){
        p = cur;
        while (p->next!=NULL){
            if(cur->data == p->next->data)
                p->next = p->next->next;
            p = p->next;
        }
        cur = cur->next;
    }
    printLinkList(head);
}




typedef char datatype;

typedef struct node {datatype data; struct node *next;}lklist;

/**
 * 设单链表中有仅三类字符的数据元素 ( 大写字母、数字和其它字符 ) ，
 * 要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
 * @param head
 * @param ha
 * @param hb
 * @param hc
 */
void split(lklist *head,lklist *ha,lklist *hb,lklist *hc){
    lklist *p;
    ha=0,hb=0,hc=0;
    for(p=head;p!=0;p=head){
        head=p->next;
        p->next=0;
        if (p->data>='A' && p->data<='Z') {
            p->next=ha;
            ha=p;
        }else if (p->data>='0' && p->data<='9') {
            p->next=hb;
            hb=p;
        } else {
            p->next=hc;
            hc=p;
        }
    }
}

/**
 * 设计两个有序单链表的合并排序算法
 * @param ha
 * @param hc
 */
void mergeLinkList( linklist ha, linklist hb,linklist hc){
    linklist s = hc = 0;
    while (ha!=0 && hb!=0){
        if(ha->data<hb->data){
            if(s==0)
                hc = s = ha;
            else{
                s->next = ha;
                s = ha;
            }
            ha = ha->next;
        }
        else{
           if(s==0)
               hc = s = hb;
           else{
               s->next = hb;
               s = hb;
           }
           hb = hb->next;
        }
    }
    if(ha==0)
        s->next = hb;
    else
        s->next = ha;
}

/**
 * 链表：设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。
 * @param A
 * @param B
 * @param C
 */
void intersection(linklist A,linklist B,linklist C)
{
    linknode *p,*q,*t;
    for(p=A,A=0;p!=0;p=p->next)   // p指针遍历链表A
    {
        for(q=B;q!=0;q=q->next)   // q指针遍历链表B，寻找与当前p指向结点数值相同的结点
            if (q->data==p->data)
                break;
        if(q!=0){   // 找到B中与A中数据相同的结点
            // 创建t结点，复制后使用头插法插入C结点
            t=(linknode *)malloc(sizeof(linknode)); // 创建
            t->data=p->data;    // 复制
            t->next=C;  // 头插法向链表中插入结点
            C=t;
        }
    }
}

/**
 * 设计判断单链表中元素是否是递增的算法
 * 算法思想：
 *        遍历链表，对比每一次当前结点和后继结点的大小
 *        (因为递增的链表，一定具备所有除尾节点之外，所有的节点的后继都比该节点的数值更大)
 * @param head
 * @return
 */
int isRiseLink(linklist head){
    linknode *p = head->next;
    linknode *q;
    while (p->next!=0){
        q = p->next;
        if(p->data<=q->data){
            p = q;
        } else
            return false;
    }
    return true;
}

/**
 *设计再链式存储结构上合并排序的算法：
 * 算法思想：
 *       合并ha和hb两个链表，hc为合成之后的链表
 *       每个链表逐个对比，没次将更小的结点放入到hc的链表中
 *       s为hc链表的尾节点，用于每次对比之后向hc链表后追加结点
 * @param ha
 * @param hb
 * @param hc
 */
void mergeSortLinkList(linklist ha,linklist hb, linklist hc){
    linklist s = hc = 0;
    while (ha!=0&&hb!=0){
        if(ha->data<hb->data){
            if(s==0){
                hc = s = ha;
            } else{
                s->next = ha;
                s = ha;
            }
            ha = ha->next;
        } else{
            if(s==0)
                hc = s = hb;
            else{
                s->next = hb;
                s = hb;
            }
            hb = hb->next;
        }
        if(ha==0)
            s->next = hb;
        else
            s->next = ha;
    }
}
#endif //TREEPROJECT_LINKLIST_H
